package algotithm.weekendrace.leetcode231.test4;

import java.util.HashMap;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/7-10:29
 * @Title 5700. 使所有区间的异或结果为零
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
    }

    final int len = 1024;
    public int minChanges(int[] nums, int k) {
        int n = nums.length, res = 0, sum = 0;
        int[][] dp = new int[k][len];
        int[] max = new int[k];
        // System.out.println(Arrays.toString(nums));
        HashMap<Integer, Integer>[] map = new HashMap[k];
        for(int i = 0; i < k; i++) {
            map[i] = new HashMap(20);
        }
        for(int i = 0; i < n; i++) {
            HashMap <Integer, Integer> tmp = map[i % k];
            tmp.put(nums[i], tmp.getOrDefault(nums[i], 0) + 1);
        }
        for(int i = 0; i < len; i++) {
            dp[0][i] = map[0].getOrDefault(i, 0);
            max[0] = Math.max(max[0], dp[0][i]);
        }
        for(int i = 1; i < k; i++) {
            for(int j = 0; j < len; j++) {
                dp[i][j] = max[i - 1];
                for(int num : map[i].keySet()) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j ^ num] + map[i].get(num));
                }
                max[i] = Math.max(max[i], dp[i][j]);
            }
        }
        // for(int i = 0; i < k; i++)
        // System.out.println(Arrays.toString(dp[i]));
        return n - dp[k - 1][0];
    }
}
